/* Copyright 2011 Tobias Marschall, Email: tm@cwi.nl 
 * 
 * This file is part of string-cover.
 *
 * string-cover is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * string-cover is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with string-cover.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <string.h>

#include "Multipliers.h"

using namespace std;

Multipliers::Multipliers(const ProblemInstance& instance) : instance(instance), values(instance.getIntervalNumbering().size()) {
	const vector<string>& strings = instance.getStrings();
	const SubstringStore& substrings = instance.getSubstrings();
	const IntervalNumbering& numbering = instance.getIntervalNumbering();
	for (size_t string_nr=0; string_nr<strings.size(); ++string_nr) {
		for (size_t i=0; i<strings[string_nr].size(); ++i) {
			for (size_t j=i+1; j<=strings[string_nr].size(); ++j) {
				size_t interval_nr = numbering.getIndex(string_nr, i, j);
				size_t substring_nr = substrings.getIndex(string_nr, i, j);
				values[interval_nr] = instance.getWeight(substring_nr) / substrings.getCount(substring_nr);
			}
		}
	}
}

Multipliers::Multipliers(const ProblemInstance& instance, const std::valarray<double>& values) : instance(instance), values(values) {
}

Multipliers::Multipliers(const Multipliers& mulipliers) : instance(mulipliers.instance), values(mulipliers.values){
}

Multipliers::~Multipliers() {
}

double Multipliers::get(size_t string_nr, size_t start_pos, size_t end_pos) const {
	const IntervalNumbering& numbering = instance.getIntervalNumbering();
	return values[numbering.getIndex(string_nr, start_pos, end_pos)];
}

void Multipliers::set(size_t string_nr, size_t start_pos, size_t end_pos, double value) {
	const IntervalNumbering& numbering = instance.getIntervalNumbering();
	values[numbering.getIndex(string_nr, start_pos, end_pos)] = value;
}

double floor_to_zero(const double& d) {
	return d>=0.0?d:0.0;
}

std::auto_ptr<Multipliers> Multipliers::adapt(double mu, double upper_bound, double lower_bound, const boost::dynamic_bitset<> & selected_substrings, const boost::dynamic_bitset<> & selected_intervals) const {
	const vector<string>& strings = instance.getStrings();
	const IntervalNumbering& intervals = instance.getIntervalNumbering();
	const SubstringStore& substrings = instance.getSubstrings();
	valarray<double> subgradients(intervals.size());
	int nonzero_subgradients = 0;
	for (size_t string_nr=0; string_nr<strings.size(); ++string_nr) {
		for (size_t i=0; i<strings[string_nr].size(); ++i) {
			for (size_t j=i+1; j<=strings[string_nr].size(); ++j) {
				size_t interval_nr = intervals.getIndex(string_nr,i,j);
				// present x-variable
				double x = selected_substrings[substrings.getIndex(string_nr,i,j)]?1.0:0.0;
				// present z-variable
				double z = selected_intervals[interval_nr]?1.0:0.0;
				subgradients[interval_nr] = x - z;
				if (x!=z) nonzero_subgradients += 1;
#ifdef DEBUG
				const string& s = strings[string_nr];
				cout << "Subgradient: "<< s.substr(0,i) << "[" << s.substr(i, j-i) << "]" << s.substr(j, s.size()-j);
				cout << ": x-z = " << x << '-' << z << " = " << subgradients[interval_nr] << endl;
#endif
			}
		}
	}
	if (nonzero_subgradients==0) {
#ifdef DEBUG
		cout << "All subgradients are zero!" << endl;
#endif
		return auto_ptr<Multipliers>(0);
	}
	double factor = mu * (upper_bound-lower_bound) / nonzero_subgradients;
#ifdef DEBUG
	cout << "Subgradient coefficient: mu * (upper_bound-lower_bound) / nonzero_subgradients = " << mu << " * ("<<upper_bound<<'-'<<lower_bound<<") / "<<nonzero_subgradients << " = " << factor << endl;
#endif
	subgradients *= factor;
	valarray<double> new_multipliers(values);
	new_multipliers -= subgradients;
	return auto_ptr<Multipliers>(new Multipliers(instance, new_multipliers.apply(floor_to_zero)));
}

void Multipliers::multiplierSums(double* result_array) {
	const vector<string>& strings = instance.getStrings();
	const SubstringStore& substrings = instance.getSubstrings();
	const IntervalNumbering& numbering = instance.getIntervalNumbering();
	memset(result_array, 0, sizeof(double)*substrings.size());
	for (size_t string_nr=0; string_nr<strings.size(); ++string_nr) {
		for (size_t i=0; i<strings[string_nr].size(); ++i) {
			for (size_t j=i+1; j<=strings[string_nr].size(); ++j) {
				size_t interval_nr = numbering.getIndex(string_nr, i, j);
				size_t substring_nr = substrings.getIndex(string_nr, i, j);
				result_array[substring_nr] += values[interval_nr];
			}
		}
	}
}

std::ostream& operator<<(std::ostream& os, const Multipliers& multipliers) {
	const vector<string>& strings = multipliers.instance.getStrings();
	for (size_t string_nr=0; string_nr<strings.size(); ++string_nr) {
		const string& s = strings[string_nr];
		for (size_t i=0; i<strings.at(string_nr).size(); ++i) {
			for (size_t j=i+1; j<=strings.at(string_nr).size(); ++j) {
				os << s.substr(0,i) << "[" << s.substr(i, j-i) << "]" << s.substr(j, s.size()-j);
				os << ": " << multipliers.get(string_nr, i, j);
				os << endl;
			}
		}
	}
	return os;
}






